import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {

    private int size;
    private int[] open;
    private WeightedQuickUnionUF uf;
    private int width;
    private int openSites;

    // creates n-by-n grid, with all sites initially blocked
    public Percolation(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("n must be > 0");
        }
        size = n * n;
        // 用一维数组储存site是否为open，0为blocked，1为open
        open = new int[size];
        // 所有site加上两个虚拟site的数据结构
        uf = new WeightedQuickUnionUF(size + 2);
        // 宽度用于降维，检查边界，连通四方
        width = n;
        openSites = 0;
    }

    // opens the site (row, col) if it is not open already
    public void open(int row, int col) {
        checkBounds(row, col);
        int num = ijTo1D(row, col);
        open[num] = 1;
        openSites++;
        connectToOpenNeighbors(row, col);
    }

    // is the site (row, col) open?
    public boolean isOpen(int row, int col) {
        checkBounds(row, col);
        int num = ijTo1D(row, col);
        return (open[num] == 1);
    }

    // is the site (row, col) full? 是否和上方虚拟节点联通
    public boolean isFull(int row, int col) {
        checkBounds(row, col);
        return uf.find(size) == uf.find(ijTo1D(row, col));
    }

    // returns the number of open sites
    public int numberOfOpenSites() {
        return openSites;
    }

    // does the system percolate?
    public boolean percolates() {
        return uf.find(size) == uf.find(size + 1);
    }

    // 检查边界
    private void checkBounds(int i, int j) {
        if (i <= 0 || i > width) {
            throw new java.lang.IllegalArgumentException("row index i out of bounds");
        }
        if (j <= 0 || j > width) {
            throw new java.lang.IllegalArgumentException("row index i out of bounds");
        }
    }

    // 降维
    private int ijTo1D(int i, int j) {
        return (i - 1) * width + j - 1;
    }

    // 连接两个site
    private void attemptUnion(int i, int j, int index) {
        if (isOpen(i, j)) {
            uf.union(ijTo1D(i, j), index);
        }
    }

    // 连接四方sites，i和j从1开始，不包括上下虚拟节点
    private void connectToOpenNeighbors(int i, int j) {
        int index = ijTo1D(i, j);
        if (j < width) attemptUnion(i, j+1, index);
        if (j > 1) attemptUnion(i, j-1, index);
        if (i < width) {
            attemptUnion(i+1, j, index);
        } else {
            // 最后一行，连通下方虚拟节点
            uf.union(index, size+1);
        }
        if (i > 1) {
            attemptUnion(i-1, j, index);
        } else {
            // 第一行，连通上方虚拟节点
            uf.union(index, size);
        }
    }

    // test client (optional)
    public static void main(String[] args) {
        Percolation perc = new Percolation(3);
        perc.open(1, 2);
        perc.open(2, 2);
        perc.open(2, 3);
        perc.open(3, 3);
        boolean c = perc.isFull(1, 1);
        boolean c1 = perc.uf.connected(perc.ijTo1D(1, 1), perc.ijTo1D(2, 1));
        boolean c2 = perc.percolates();
        StdOut.println(c);
        StdOut.println(c1);
        StdOut.println(c2);
    }
}
